package com.ai.dmc.index.common.util;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author xiong.xu 用于聚类分组，确定边界
 */
public class BasicKMeans {

	/**
	 * 避免死循环--设置分组最大次数
	 */
	private static final int MAX_REPEAT_NUM = 100;
	
	public static void main(String[] args) {
		
		double[] p = { 79.0, 35.0, 20.0, 17.0, 17.0, 9.0, 8.0, 5.0, 2.0,
		2.0, 2.0, 2.0, 2.0, 1.0,1.0,1.0,1.0};
		
		//double[] p = { 1, 1.2, 2346430.28, 2211137.36 };
		int k = 5;
		double[][] g;

		// 聚类结果
		/*
		 * g = cluster(p, k); for (int i = 0; i < g.length; i++) { for (int j =
		 * 0; j < g[i].length; j++) { System.out.print(g[i][j]);
		 * System.out.print("\t"); } System.out.println(); }
		 */

		// 边界信息
		List<Double> result = getGroupEdgeValue(p, k);
		for (Double v : result) {
			System.out.print(v + "---");
		}
	}

	/**
	 * 根据values 返回边界值<br/>
	 * 返回边界[最小值,最大值]
	 */
	public static List<Double> getGroupEdgeValue(double[] values, int k) {
		List<Double> result = new ArrayList<Double>();
		if (values == null || values.length < 1) {
			return result;
		}

		// 元素小于预期质心数，采用等分分级
		if (values.length < k) {
			return average(values, k);
		}

		// 元素去重后小于预期质心数，采用等分分级
		Set<Double> varTypeSet = new HashSet<Double>();
		for (int i = 0; i < values.length; i++) {
			varTypeSet.add(values[i]);
		}
		
		int i = 0;
		double[] vars = new double[varTypeSet.size()];
		for (Double var : varTypeSet) {
			vars[i++] = var;
		}
		
		if (varTypeSet.size() <= k) {
			return average(vars, k);
		}

		double[][] g = cluster(values, k,vars);
		for (i = 0; i < g.length; i++) {
			if( g[i].length == 0){
				result.add(0.0);
				result.add(0.0);
				continue;
			}
			
			double[] edgeValue = valueEdge(g[i]);

			result.add(edgeValue[0]);
			result.add(edgeValue[1]);
		}

		Collections.sort(result);

		return result;
	}

	/**
	 * 给定 double 类型数组，返回边界[最小值,最大值]。<br/>
	 */
	private static double[] valueEdge(double[] p) {
		double[] edge = { p[0], p[0] };
		if (p.length == 1) {
			return edge;
		}

		for (int i = 1; i < p.length; i++) {
			if (p[i] < edge[0]) {
				edge[0] = p[i];
			}

			if (p[i] > edge[1]) {
				edge[1] = p[i];
			}
		}
		return edge;
	}

	/**
	 * 聚类函数主体。 针对一维 double 数组。指定聚类数目 k。 将数据聚成 k 类。
	 */
	private static double[][] cluster(double[] p, int k,double[] centerVars) {
		
		int num = 0;
		
		// 存放聚类旧的聚类中心
		double[] c = new double[k];
		// 存放新计算的聚类中心
		double[] nc = new double[k];
		// 存放放回结果
		double[][] g = null;
		// 初始化聚类中心
		// 经典方法是随机选取 k 个
		// 本例中采用前 k 个作为聚类中心
		// 聚类中心的选取不影响最终结果
		
		for (int i = 0; i < k; i++){
			c[i] = centerVars[i];
		}
		
		// 循环聚类，更新聚类中心
		// 到聚类中心不变为止
		while ( num < MAX_REPEAT_NUM ) {
			// 根据聚类中心将元素分类
			g = group(p, c);
			// 计算分类后的聚类中心
			for (int i = 0; i < g.length; i++) {
				if( g[i].length != 0 ){
					nc[i] = center(g[i]);
				}else{
					nc[i] = 1.0;
				}
			}
			// 如果聚类中心不同
			if (!equal(nc, c)) {
				// 为下一次聚类准备
				c = nc;
				nc = new double[k];
			} else {
				// 聚类结束
				break;
			}
			
			num++;
		}
		// 返回聚类结果
		return g;
	}

	/**
	 * 聚类中心函数 简单的一维聚类返回其算数平均值 可扩展
	 */
	private static double center(double[] p) {
		return sum(p) / p.length;
	}

	/**
	 * 给定 double 型数组 p 和聚类中心 c。 根据 c 将 p 中元素聚类。返回二维数组。 存放各组元素。
	 */
	private static double[][] group(double[] p, double[] c) {
		// 中间变量，用来分组标记
		int[] gi = new int[p.length];
		// 考察每一个元素 pi 同聚类中心 cj 的距离
		// pi 与 cj 的距离最小则归为 j 类
		for (int i = 0; i < p.length; i++) {
			// 存放距离
			double[] d = new double[c.length];
			// 计算到每个聚类中心的距离
			for (int j = 0; j < c.length; j++) {
				d[j] = distance(p[i], c[j]);
			}
			// 找出最小距离
			int ci = min(d);
			// 标记属于哪一组
			gi[i] = ci;
		}
		// 存放分组结果
		double[][] g = new double[c.length][];
		// 遍历每个聚类中心，分组
		for (int i = 0; i < c.length; i++) {
			// 中间变量，记录聚类后每一组的大小
			int s = 0;
			// 计算每一组的长度
			for (int j = 0; j < gi.length; j++)
				if (gi[j] == i)
					s++;
			// 存储每一组的成员
			g[i] = new double[s];
			s = 0;
			// 根据分组标记将各元素归位
			for (int j = 0; j < gi.length; j++)
				if (gi[j] == i) {
					g[i][s] = p[j];
					s++;
				}
		}
		// 返回分组结果
		return g;
	}

	/**
	 * 计算两个点之间的距离， 这里采用最简单得一维欧氏距离， 可扩展。
	 */
	private static double distance(double x, double y) {
		return Math.abs(x - y);
	}

	/**
	 * 返回给定 double 数组各元素之和。
	 */
	private static double sum(double[] p) {
		double sum = 0.0;
		for (int i = 0; i < p.length; i++)
			sum += p[i];
		return sum;
	}

	/**
	 * 给定 double 类型数组，返回最小值的下标。
	 */
	private static int min(double[] p) {
		int i = 0;
		double m = p[0];
		for (int j = 1; j < p.length; j++) {
			if (p[j] < m) {
				i = j;
				m = p[j];
			}
		}
		return i;
	}

	/**
	 * 判断两个 double 数组是否相等。 长度一样且对应位置值相同返回真。
	 */
	private static boolean equal(double[] a, double[] b) {
		if (a.length != b.length)
			return false;
		else {
			for (int i = 0; i < a.length; i++) {
				if (a[i] != b[i])
					return false;
			}
		}
		return true;
	}

	
	/**
	 * 给定 double 类型数组，返回最大值和最小值
	 */
	private static double[] getMinMaxValue(double[] p) {
		double[] result = new double[2];
		double min = p[0];
		double max = p[0];
		for (int i = 1; i < p.length; i++) {
			if (p[i] > max) {
				max = p[i];
			}
			
			if (p[i] < min) {
				min = p[i];
			}
		}
		
		result[0] = min;
		result[1] = max;
		return result;
	}
	
	/**
	 * @Description : 对一组数据，进行等分分级
	 * 
	 * @return List<Double> 边界值
	 *
	 * @author : xuxiong
	 * @date : 2015年12月8日 下午3:15:31
	 * 
	 */
	private static List<Double> average(double[] a, int k) {
		List<Double> result = new ArrayList<Double>();

		double[] minMaxValue = getMinMaxValue(a);

		double averageNum = (minMaxValue[1]-minMaxValue[0]) / k;

		double leftValue  = 0.0;
		double rightValue = 0.0;
		for (int i = 0; i < k; i++) { // 产生 2*k 个边界值[min,max]
			leftValue = minMaxValue[0] + i * averageNum;
			rightValue = minMaxValue[0] + (i+1) * averageNum;
			result.add(leftValue);
			result.add(rightValue);
		}

		return result;
	}
}
